#include <stdio.h>
#include <stdlib.h>


int size=0;//Number of members
//////////////////
///Structure//////
//////////////////
struct node
	{
	int value;
	struct node * next;
	}*list,*rear;
	
	
/////////////////////
////To Clear Memory//
/////////////////////


void clearmemory()
{
	while(list!=NULL)
		{
		rear=list;
		list=list->next;
		free(rear);
		}
}
///////////////////////////////////////////////////////
/////To Append and extend numbers in a list////////////
///////////////////////////////////////////////////////

void appendlist(int num)		//////Appending has been done at the end of the link-list
	{
	//size++;
	struct node *newnode;
	newnode=malloc(sizeof(struct node *));		
	if(newnode==NULL)
		{
		printf("ERROR!!!NO MEMORY AVAILABLE");
		clearmemory();
		}
	else
		{
		size++;
		newnode->value=num;
		newnode->next=NULL;
		if(list==NULL)			/////For first element
			list=rear=newnode;
		else
			{
			rear->next=newnode;
			rear=newnode;	
			}
		}
	}

//////////////////////////////////////////////
/////Work on Extend yet to be done i.e.///////
///////i.e.extending a list not number////////
//////////////////////////////////////////////

/////////////////////////////////////////////////////
/////Inserting a Number in the middle of the list////
/////////////////////////////////////////////////////

void insertlist(int pos,int num)
	{
	struct node *cur, *prev, *newnode;
	int i=0;
	if(pos>size+1 || pos<1)
		printf("ERROR!!!!INVALID POSITION");
	else
		{
		newnode=malloc(sizeof(struct node));
		if(newnode==NULL)
			{
			printf("ERROR!!!NO MEMORY AVAILABLE");
			clearmemory();
			}
		else
			{
			size++;
			newnode->value=num;
			newnode->next=NULL;
			if(list==NULL)		////first node
				{
				list=newnode;
				}
			else
				{
				for(cur=list;i<pos-1;prev=cur,cur=cur->next,i++);		///cur ends up to the position where num is to be inserted
												////And prev to the prev node
				if(pos==1)
					{
					newnode->next=list;
					list=newnode;
					}
				else if(pos==size+1)			//for last node
					rear->next=newnode;				
				else
					{
					newnode->next=cur;
					prev->next=newnode;
					}
				}
			}
		}
	}
/////////////////////////////
///TO DISPLAY THE LIST///////
/////////////////////////////
void displaylist()
	{
	struct node *temp;
	printf("\n");
	for(temp=list;temp!=NULL;temp=temp->next)
		{
		printf("%d->",temp->value);
		}
	printf("\n");
	}
////////////////////////////////////////
///TO REMOVE A NUMBER FROM THE LIST/////
////////////////////////////////////////
void removelist(int num)
	{
	struct node *cur, *prev;
	int flag;
	flag=0;
	if(list!=NULL && list->value==num)				////If first node is to be removed
		{
		cur=list;
		list=list->next;
		free(cur);
		flag=1;
		}
	else					//////For any other node
		{
		for(cur=list;cur!=NULL;prev=cur,cur=cur->next)
			{
			if(cur->value==num)
				{
				prev->next=cur->next;
				free(cur);
				size--;
				flag=1;
				break;
				}
			}
			
		}
	if(flag==0)
		printf("ERROR: NUMBER NOT IN LIST!!!!!\n");
	}
	
////////////////////////////////////////////////
///TO REMOVE A NUMBER FROM THE GIVEN INDEX//////
////////////////////////////////////////////////
int poplist(int pos)
	{
	int element,i;
	struct node *temp, *temp1;
	if(pos<=size && pos>0)
		{
		temp=list;
		if(pos==1)		/////to remove fst number
			{
			element=temp->value;	
			list=list->next;			
			free(temp);
			}
		else
			{
			for(i=2;i<pos;i++)	///to reach to a node before the one which is to be removed
				temp=temp->next;
			temp1=temp->next;
			if(temp1->next==NULL)	////if last node is to be removed
				temp->next=NULL;
			else			/////for any other node in the middle of d list
				temp->next=temp1->next;
			element=temp1->value;
			free(temp1);
			}
		return element;
		}
	else
		{
		element=-1;	/////-1 means invalid pos
		return element;
		printf("ERROR:INVALID POSITION!!!!");
		}
	}
//////////////////////////////////////////////////////////
///////TO KNOW WAT IS THE VALUE AT A GIVEN POSITION///////
//////////////////////////////////////////////////////////
int indexlist(int pos)
	{
	int i=0;
	struct node *temp;
	if(pos<=size && pos>0)
		{
		temp=list;
		for(i=1;i<=pos;i++)
			temp=temp->next;
		printf("Element at position %d is %d",pos,temp->value);
		return temp->value;
		}
	else
		printf("Error!!!INVALID POSITION");
		return -1;
	}



///////////////////////////////////////////
/////TO SORT A LIST ON BASIS OF VALUES/////
///////////IN ASCENDING ORDER//////////////
///////////////////////////////////////////

void sortlist()
	{
	if(list==NULL)
		{
		clearmemory();
		printf("ERROR!!!!No number in the list...Terminating!!!!");
		exit(0);
		}
	struct node *a, *b, *c, *d, *tmp;
	a=b=c=d=tmp=NULL;
	
	while(d != list->next)
		{
		c = a = list;
		b = a->next;
		while(b != d)
			{
			if(a->value > b->value)		//bubble sort
				{
				if(a == list)		//if it is a first node
					{
					tmp = b -> next;	//swapping
					b->next = a;
					a->next = tmp;
					list = b;
					c = b;
					}
				else			//if node is not the first one
					{
					tmp = b->next;
					b->next = a;
					a->next = tmp;
					c->next = b;
					c = b;
					}
				}
			else			//if order is correct
				{
				c = a;
				a = a->next;
				}
			b = a->next;
			if(b == d)		//if first pass of bubble sort is done
				d = a;
			}
		}
	}
////////////////////////////////////
/////FOR REVERSING A GIVEN LIST/////
////////////////////////////////////

void reverselist()	
	{
	struct node *a,*b,*c;
	a=list;
	b=c=NULL;
	//changing d linking one by one i.e. if list is 1->2->3 den
	// fst pass 1->NULL 2->3 wid a hving 2 nd c hving 1 
	// 2nd pass 1<-2 wid a having 3 nd c hving 2
	// 3rd pass 1<-2<-3 wid a hving NULL and c hving 3
	// list reversed
	while (a)
		{
		list=a; 		
		b=a->next; // saving d nxt ptr in b
		a->next=c; // changing next 2 previous
		c=a;
		a=b;
		}
	}
//////////////////////////////////////////////////////
////TO FIND COUNT OF A GIVEN NUMBER IN THE LIST///////
//////////////////////////////////////////////////////
int count(int num)
	{
	struct node *temp;
	int ctr;
	ctr=0;
	for(temp=list;temp!=NULL;temp=temp->next)
		{
		if(temp->value==num)
			ctr++;
		}
	return ctr;
	}



	
///////////////////////////////////////////////////////
////////////  /\  /\      /\    |   /\    /  //////////
//////////// /  \/  \    /__\   |  /  \  /  ///////////
/////////// /        \  /    \  | /    \/  ////////////
///////////////////////////////////////////////////////
int main(void)
	{
	system("clear");
	int pos=0;
	int choice=1;
	int i=0;
	int *list1;
	while(choice)
		{
		printf("\nEvery Count or index or anything starts from 1\n");
		printf("1)Append\n2)Extend\n3)Insert\n4)Remove\n5)Poplastelement\n6)Pop\n7)Index\n8)Count\n9)Sort\n10)Reverse\n0)Exit\nYour Choice ");
		scanf(" %d",&choice);
		switch(choice)
			{
			case 1:
				{
				printf("Enter number to append");
				scanf("%d",&pos);//Actually its not position(pos) but a number
				appendlist(pos);
				break;
				}
			case 2:
				{
				printf("Enter no. of elements you would like to Extend in the List");
				scanf("%d",&pos);//Total numbers to be extended
					while(pos!=0)//Its a number not position
						{
						printf("Enter the number");
						scanf(" %d",&i);//Numbers to be extended
						appendlist(i);//Its a number
						pos--;
						}
				break;
				}
			case 3:
				{
				printf("Enter Position");
				scanf(" %d",&pos);
				printf("Enter Number");
				scanf(" %d",&i);//Number
				insertlist(pos,i);
				break;
				}
			case 4:
				{
				printf("Enter number to be removed");
				scanf("%d",&pos);	//pos is a number	
				removelist(pos);
				break;
				}
			case 5:
				{
				pos=poplist(size);//pos represents element poped not position
				if(pos!=-1)	//user must not enter -1;
					printf("Element Removed %d",pos);
				break;
				}
			case 6:
				{
				printf("Enter position to be poped out");
				scanf("%d",&pos);//this pos is for position
				pos=poplist(pos);//pos on l.h.s. represents element poped not position
				printf("Element Removed %d",pos);
				break;
				}
			case 7:
				{
				printf("Enter Index: ");
				scanf("%d",&pos);
				pos=indexlist(pos);	//here pos has the element
				break;
				}
			case 8:
				{
				printf("Enter Integer");
				scanf("%d",&pos);	//here pos is value whose count is to be found
				pos=count(pos);		//here pos on l.h.s. has the count
				break;
				}
			case 9:
				{
				sortlist();
				break;
				}
			case 10:
				{
				reverselist();
				break;
				}
			
			default:
				{
				clearmemory();
				break;
				}
			}
		displaylist();
		}
	return 0;
	}	
